1. Field of the Invention
This invention relates to a wiring-pattern-determination system for designing wiring patterns of a PC board or LSI chip based on maze running.
2. Background of the Related Art
For instance, the problem of large scale combination including LSI CAD such as of wiring processing requires very high speed processing. The method can be speeded up by high speed processing of a massively parallel computer containing numerous processors.
Maze running is an algorithm to find a path of two points in the shortest length, and is widely used for routing patterns of a PC board or LSI chip. In maze running, the plane in consideration comprises grid points which are wiring units. The source (originating point) and target (end point) are set on grid points in the first stage. Then a labeling and a back-trace are used to determine the wiring pattern (net). Here, the labeling assigns the label n+1 to a grid point neighboring the nth empty (without an interference) grid point from the source, e.g., assigning label 1 to an empty grid point neighboring the source and assigning label 2 to an empty grid point neighboring the grid point assigned to label 1, until there is no more neighboring grid point or the label has reached the target. A back-trace traces back each grid point assigned to a label starting from the target to the source so that the numbers of the labels assigned to each grid point are reduced by one.
Recently, as the PC board and LSI chip are increasing in density, the amount of data in consideration by maze running, i.e., the data scale handled, is increased. Then the speed up of a wiring processing is desired, and a specialized hardware and parallel processing has been tried.
For instance, a processor is assigned in one-to-one correspondence to each grid point and a communication port connects between neighboring processors. Each processor on a wavefront (the grid point with the same label) is parallel activated in labeling, and labels to the neighboring processors travel done in parallel. The processor on the wavefront processes in parallel to speed up the method.
However, it is a problem that the back-trace cannot be speeded up by the parallel processing easily.
In the back trace, a wiring path is determined by tracing back to the processor corresponding to the source via the label assigned in the labeling from the processor corresponding to the target. While only two processors communicate information of the path, all other processors are standing by at a particular point in time. Hence, a disadvantage of the parallelism exists in the processing not fully exploited as a whole.